package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-18 10:46
 **/
public class LeetCode142 {

    /**
     * 使用Floyd判圈的结论解决环形链表的问题 detect:探测
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        //慢指针
        ListNode slow = head;
        //快指针
        ListNode fast = head;
        // 这边要先走一次，再判断，不然刚开始就满足条件，就出bug了，找了半天
        do {
            fast = fast.next.next;
            slow = slow.next;
        } while (fast != null && fast.next != null && fast != slow);

        if (fast == null || fast.next == null) {
            return null;
        }
        //指向头结点
        ListNode before = head;
        //指向重合的结点
        ListNode after = fast;
        while (before != after) {
            before = before.next;
            after = after.next;
        }
        return before;
    }

    public static void main(String[] args) {

    }
}
